package Leetcode.数组字符串;

/**
 * @Author: kirito
 * @Date: 2024/3/15 19:53
 * @Description:
 *
 */

public class MaxHeap {
    private int[] heap;
    private int size;

    public MaxHeap(int[] array) {
        heap = array;
        size = array.length;
        buildHeap();
    }

    private void buildHeap() {
        for (int i = heap.length / 2 - 1; i >= 0; i--) {
            heapify(i);
        }
    }

    private void heapify(int i) {
        int largest = i;
        int left = leftChild(i);
        int right = rightChild(i);

        if (left < size && heap[left] > heap[largest]) {
            largest = left;
        }

        if (right < size && heap[right] > heap[largest]) {
            largest = right;
        }

        if (largest != i) {
            swap(i, largest);
            heapify(largest);
        }
    }

    private int leftChild(int i) {
        return 2 * i + 1;
    }

    private int rightChild(int i) {
        return 2 * i + 2;
    }

    private void swap(int i, int j) {
        int temp = heap[i];
        heap[i] = heap[j];
        heap[j] = temp;
    }

    public int extractMax() {
        int max = heap[0];
        heap[0] = heap[size - 1];
        size--;
        heapify(0);
        return max;
    }

    public int getMax() {
        return heap[0];
    }

    public int size() {
        return size;
    }

    public static void main(String[] args) {
        int[] array = {12, 11, 13, 5, 6, 7};
        MaxHeap maxHeap = new MaxHeap(array);

        System.out.println("Max Heap array: ");
        for (int i : maxHeap.heap) {
            System.out.print(i + " ");
        }
        System.out.println();

        System.out.println("elements:");
        while (maxHeap.size() > 0) {
            System.out.println(maxHeap.extractMax());
        }
    }
}
